import java.util.List;

public class MyLinkedList implements ILinkedList{

    static class ListNode {//结点
        public int val;//数据域
        public ListNode prev;//放前一个地址
        public ListNode next;//放下一个地址

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;
    public ListNode last;

    @Override
    public void addFirst(int val) {
        ListNode node = new ListNode(val);
        //空链表的时候
        if(head == null) {
            head = node;
            last = node;
            return;
        }
        node.next = head;
        head.prev = node;
        head = node;
    }

    @Override
    public void addLast(int val) {
        ListNode node = new ListNode(val);
        if(head == null) {
            head = node;
            last = node;
            return;
        }
        last.next = node;
        node.prev = last;
        last = node;
    }

    @Override
    public void addIndex(int index, int val) {
        ListNode node = new ListNode(val);
        //1.空链表
        if(head == null) {
            head = node;
            last = node;
            return;
        }
        //2.位置是否异常
        if(index < 0 || index > size()) {
            System.out.println("插入位置非法！");
            return;
        }
        //3.头插的清空
        if(index == 0) {
            addFirst(val);
            return;
        }
        //4.尾插情况
        if(index == size()) {
            addLast(val);
            return;
        }
        //5.中间位置插入
        //5.1先找到插入位置的前驱
        ListNode cur = find(index);
        node.next = cur.next;
        cur.next.prev = node;
        cur.next = node;
        node.prev = cur;
    }
    private ListNode find(int index) {
        ListNode cur = head;
        int count = index-1;
        while(count != 0) {
            cur = cur.next;
            count--;
        }
        return cur;
    }
    @Override
    public boolean contains(int key) {
        //查找key元素是否存在
        ListNode cur = head;
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        //删掉key
       /* //1.找到key的结点
        ListNode cur = finds(key);
        //2.判断
        if(cur == null) {
            System.out.println("链表中不存在key元素");
            return;
        }
        //存在key

        //3.只有一个结点
        if(head == last) {
            head =null;
            last = null;
            return;
        }
        //4.删除的头节点
        if(cur == head) {
            head = head.next;
            head.prev = null;
            return;
        }
        //5.删除尾结点
        if(cur == last) {
            last = last.prev;
            last.next = null;
            return;
        }
        //6.删除
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
*/
       ListNode cur = head;
       while(cur != null) {
            if(cur.val == key) {
                //找到了
                //1.只有一个结点
                if(head == last) {
                    head =null;
                    last = null;
                    return;
                }
                //2.删除的头节点
                if(cur == head) {
                    head = head.next;
                    head.prev = null;
                    return;
                }
                //3.删除尾结点
                if(cur == last) {
                    last = last.prev;
                    last.next = null;
                    return;
                }
                //4.中间位置删除
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                return;
            }
            cur = cur.next;
       }
        System.out.println("链表中不存在"+key);
    }
    private ListNode finds(int key) {
        ListNode cur = head;
        while(cur != null) {
            if(cur.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    @Override
    public void removeAllkey(int key) {
        //删除所有的key元素
        ListNode cur = head;
        while(cur != null) {
            if(cur.val == key) {
                //找到了
                if(head == last) {
                    head =null;
                    last = null;
                } else if(cur == head) {
                    head = head.next;
                    head.prev = null;
                } else if(cur == last) {
                    last = last.prev;
                    last.next = null;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            cur = cur.next;
        }
        System.out.println("链表中不存在"+key+"or"+key+"已被删完");

    }

    @Override
    public int size() {
        int count = 0;
        ListNode cur = head;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    @Override
    public void display() {
        ListNode cur = head;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }

    @Override
    public void clear() {
        last = null;
        head = null;
    }//双向链表

}
